home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Utilities / Type1Manager / src / regions.c < prev    next >
C/C++ Source or Header  |  1998-05-22  |  47KB  |  1,762 lines
  1. /* $XConsortium: regions.c,v 1.6 94/02/06 16:22:21 gildea Exp $ */
  2. /* Copyright International Business Machines, Corp. 1991
  3.  * All Rights Reserved
  4.  * Copyright Lexmark International, Inc. 1991
  5.  * All Rights Reserved
  6.  *
  7.  * License to use, copy, modify, and distribute this software and its
  8.  * documentation for any purpose and without fee is hereby granted,
  9.  * provided that the above copyright notice appear in all copies and that
  10.  * both that copyright notice and this permission notice appear in
  11.  * supporting documentation, and that the name of IBM or Lexmark not be
  12.  * used in advertising or publicity pertaining to distribution of the
  13.  * software without specific, written prior permission.
  14.  *
  15.  * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
  16.  * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
  17.  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
  18.  * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
  19.  * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
  20.  * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
  21.  * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
  22.  * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
  23.  * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  24.  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  25.  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  26.  * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
  27.  * THIS SOFTWARE.
  28.  */
  29.  
  30. /*
  31.  * REGIONS Module - Regions Operator Handler
  32.  *
  33.  * This module is responsible for creating and manipulating regions.
  34.  *
  35.  * &author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
  36.  */
  37.  
  38.  
  39. /*
  40.  * Include Files
  41.  *
  42.  * The included files are:
  43.  */
  44. #ifndef T1GST
  45. #include "global.h"
  46. #endif
  47.  
  48. #include <stdio.h>
  49.  
  50. /**
  51.  * Prototypes for static functions
  52.  **/
  53. static struct edgelist *NewEdge(
  54.         pel xmin, int xmax,        /* X extent of edge */
  55.         pel ymin, int ymax,        /* Y extent of edge */
  56.         pel *xvalues,            /* list of X values for entire edge */
  57.         int isdown);            /* flag:  TRUE means edge progresses downward */
  58.  
  59. static struct edgelist *swathxsort(
  60.         struct edgelist *before0,     /* edge before this swath */
  61.         struct edgelist *edge);        /* input edge */
  62.  
  63. static void Unwind(
  64.         struct edgelist *area);    /* input area modified in place */
  65.  
  66. static void __stdargs newfilledge(
  67.         struct region *R,        /* region being built */
  68.         fractpel xmin,
  69.         fractpel xmax,            /* X range of this edge */
  70.         fractpel ymin,
  71.         fractpel ymax,            /* Y range of this edge */
  72.         int isdown);            /* flag:  TRUE means edge goes down, else up */
  73.  
  74. static struct edgelist *splitedge(
  75.         struct edgelist *list,    /* area to split */
  76.         pel y);                    /* Y value to split list at */
  77.  
  78. static void vertjoin(struct edgelist *top, struct edgelist *bottom);
  79. static int touches(int h, pel *left, pel *right);
  80. static int crosses(int h, pel *left, pel *right);
  81. static void cedgemin(int h, pel *e1, pel x);
  82. static void cedgemax(int h, pel *e1, pel x);
  83. static void edgemin(int h, pel *e1, pel *e2);
  84. static void edgemax(int h, pel *e1, pel *e2);
  85. static void discard(struct edgelist *left, struct edgelist *right);
  86. static void edgecheck(struct edgelist *edge, int oldmin, int oldmax);
  87. static void OptimizeRegion(struct region *R);
  88.  
  89.  
  90. /*
  91.  * The ISOPTIMIZED flag tells us if we've put a permanent region in
  92.  * 'optimal' form.
  93.  */
  94. #define   ISOPTIMIZED(flag)    ((flag)&0x10)
  95.  
  96.  
  97. /*
  98.  * "INFINITY" - A Constant Region Structure of Infinite Extent
  99.  *
  100.  * Infinity is the complement of a null area:
  101.  * Note - removed the refcount = 1 init, replaced with references = 2 3-26-91 PNM
  102.  */
  103. //static struct region infinity =
  104. //{
  105. //    REGIONTYPE,
  106. //    ISCOMPLEMENT(ON) + ISINFINITE(ON) + ISPERMANENT(ON) + ISIMMORTAL(ON), 2,
  107. //    0, 0, 0, 0,
  108. //    0, 0, 0, 0,
  109. //    NULL, NULL,
  110. //    0, 0, 0, 0, 0, NULL, NULL,
  111. //    NULL, 0, NULL, NULL
  112. //};
  113. //struct region *INFINITY = &infinity;
  114.  
  115.  
  116. /*
  117.  * "EmptyRegion" - A Region Structure with Zero Area
  118.  *
  119.  * This structure is used to initialize the region to be built in
  120.  * Interior():
  121.  * Note - replaced refcount = 1 init with references = 2 3-26-91 PNM
  122.  */
  123. struct region EmptyRegion =
  124. {
  125.     REGIONTYPE,
  126.     ISPERMANENT(ON) + ISIMMORTAL(ON), 2,
  127.     0, 0, 0, 0,
  128.     MAXPEL, MAXPEL, MINPEL, MINPEL,
  129.     NULL, NULL,
  130.     0, 0, 0, 0, 0, NULL, NULL,
  131.     NULL, 0, NULL, NULL
  132. };
  133.  
  134.  
  135. /*
  136.  * KillRegion() - Destroys a Region
  137.  *
  138.  * KillRegion nominally just decrements the reference count to that region.
  139.  * If the reference count becomes 0, all memory associated with it is
  140.  * freed.  We just follow the linked list, freeing as we go, then kill any
  141.  * associated (thresholded) picture.
  142.  * Note - added conditional return based on references 3-26-91 PNM
  143.  */
  144. void t1_KillRegion(
  145.         struct region *area)    /* area to free */
  146. {
  147.     struct edgelist *p;        /* loop variable */
  148.     struct edgelist *next;    /* loop variable */
  149.  
  150.     if (area->references < 0)
  151.         t1_abort("KillRegion:  negative reference count");
  152.     if ((--(area->references) > 1) ||
  153.         ((area->references == 1) && !ISPERMANENT(area->flag)))
  154.         return;
  155.  
  156.     for (p = area->anchor; p != NULL; p = next)
  157.     {
  158.         next = p->link;
  159.         Free(p);
  160.     }
  161.     if (area->thresholded != NULL)
  162.         KillPicture(area->thresholded);
  163.     Free(area);
  164. }
  165.  
  166.  
  167. /*
  168.  * CopyRegion() - Makes a Copy of a Region
  169.  */
  170. struct region *t1_CopyRegion(
  171.         struct region *area)    /* region to duplicate */
  172. {
  173.     struct region *r;            /* output region built here */
  174.     struct edgelist *last;        /* loop variable */
  175.     struct edgelist *p, *newp;    /* loop variables */
  176.  
  177.     r = (struct region *)Allocate(sizeof(struct region), area, 0);
  178.  
  179.     r->anchor = NULL;
  180.  
  181.     for (p = area->anchor; VALIDEDGE(p); p = p->link)
  182.     {
  183.         newp = NewEdge(p->xmin, p->xmax, p->ymin, p->ymax, p->xvalues, ISDOWN(p->flag));
  184.         if (r->anchor == NULL)
  185.             r->anchor = last = newp;
  186.         else
  187.             last->link = newp;
  188.  
  189.         last = newp;
  190.     }
  191.  
  192.     if (area->thresholded != NULL)
  193.         /* replaced DupPicture with Dup() 3-26-91 PNM */
  194.         r->thresholded = (struct picture *)Dup(area->thresholded);
  195.     return (r);
  196. }
  197.  
  198.  
  199. /*
  200.  * NewEdge() - Allocates and Returns a New "edgelist" Structure
  201.  *
  202.  * We allocate space for the X values contiguously with the 'edgelist'
  203.  * structure that locates them.  That way, we only have to free the
  204.  * edgelist structure to free all memory associated with it.  Damn
  205.  * clever, huh?
  206.  */
  207. static struct edgelist *NewEdge(
  208.         pel xmin, int xmax,        /* X extent of edge */
  209.         pel ymin, int ymax,        /* Y extent of edge */
  210.         pel *xvalues,            /* list of X values for entire edge */
  211.         int isdown)                /* flag:  TRUE means edge progresses downward */
  212. {
  213.     static struct edgelist template =
  214.     {
  215.         EDGETYPE, 0, 1, NULL, NULL,
  216.         0, 0, 0, 0, NULL
  217.     };
  218.  
  219.     struct edgelist *r;            /* returned structure */
  220.     int iy;                        /* ymin adjusted for 'long' alignment purposes */
  221.  
  222.     IfTrace2((RegionDebug), "....new edge: ymin=%d, ymax=%d ", (long)ymin, (long)ymax);
  223.     if (ymin >= ymax)
  224.         t1_abort("newedge: height not positive");
  225.  
  226.     /*
  227.      * We are going to copy the xvalues into a newly allocated area.  It
  228.      * helps performance if the values are all "long" aligned.  We can test
  229.      * if the xvalues are long aligned by ANDing the address with the
  230.      * (sizeof(long) - 1)--if non zero, the xvalues are not aligned well.  We
  231.      * set 'iy' to the ymin value that would give us good alignment:
  232.      */
  233.     iy = ymin - (((int)xvalues) & (sizeof(long) - 1)) / sizeof(pel);
  234.  
  235. //if ((ymax-iy) < 0)
  236. //    printf("EdgeList: ymax - iy < 0 : ymin=%d,ymax=%d,xvalues=%d\n",ymin,ymax,(int)xvalues);
  237.  
  238.     r = (struct edgelist *)Allocate(sizeof(struct edgelist), &template, (ymax - iy) * sizeof(pel));
  239.  
  240.     if (isdown)
  241.         r->flag = ISDOWN(ON);
  242.  
  243.     r->xmin = xmin;
  244.     r->xmax = xmax;
  245.     r->ymin = ymin;
  246.     r->ymax = ymax;
  247.  
  248.     r->xvalues = (pel *) FOLLOWING(r);
  249.     if (ymin != iy)
  250.     {
  251.         r->xvalues += ymin - iy;
  252.         xvalues -= ymin - iy;
  253.     }
  254.  
  255.     /*
  256.      * We must round up (ymax - iy) so we get the ceiling of the number of
  257.      * longs.  The destination must be able to hold these extra bytes because
  258.      * Allocate() makes everything it allocates be in multiples of longs.
  259.      */
  260.     LONGCOPY(&r[1], xvalues, (ymax - iy) * sizeof(pel) + sizeof(long) - 1);
  261.  
  262.     IfTrace1((RegionDebug), "result=%x\n", r);
  263.     return (r);
  264. }
  265.  
  266.  
  267. /*
  268.  * Building Regions
  269.  *
  270.  * Interior() - Iterate Through a Path, Building a Region
  271.  *
  272.  * This routine is the workhorse driver routine that iterates through a
  273.  * path, calling the appropriate stepping routines to actually produce the
  274.  * run end "edgelist" structures.
  275.  *
  276.  * "Interior" calls StepLine or StepConic or StepBezier as appropriate
  277.  * to produce run ends.
  278.  *
  279.  * Occasionally these routines will notice a change in Y direction
  280.  * and will call ChangeDirection (through the GOING_TO macro); this is
  281.  * a call back to the REGIONS module.
  282.  *
  283.  * ChangeDirection will call whatever function is in the region
  284.  * structure; for Interior, this function is 'newfilledge'.
  285.  *
  286.  * Newfilledge will call NewEdge to create a new edgelist structure,
  287.  * then, call SortSwath to sort it onto the linked list being built at
  288.  * the region "anchor".
  289.  *
  290.  * By making the function called by ChangeDirection be a parameter of the
  291.  * region, we allow the same ChangeDirection logic to be used by stroking.
  292.  */
  293. struct region *Interior(
  294.         struct segment *p,        /* take interior of this path */
  295.         int fillrule)            /* rule to follow if path crosses itself */
  296. {
  297.     fractpel x, y;                /* keeps ending point of path segment */
  298.     fractpel lastx, lasty;        /* previous x,y from path segment before */
  299.     struct region *R;            /* region I will build */
  300.     struct segment *nextP;        /* next segment of path */
  301.     struct fractpoint hint;        /* accumulated hint value */
  302.     char tempflag;                /* flag; is path temporary? */
  303.     char Cflag;                    /* flag; should we apply continuity? */
  304.  
  305.     IfTrace2((MustTraceCalls), ".  INTERIOR(%z, %d)\n", p, (long)fillrule);
  306.  
  307.     if (p == NULL)
  308.         return (NULL);
  309.  
  310.     /*
  311.      * Establish the 'Cflag' continuity flag based on user's fill rule and
  312.      * our own 'Continuity' pragmatic (0: never do continuity, 1: do what
  313.      * user asked, >1: do it regardless).
  314.      */
  315.     if (fillrule > 0)
  316.     {
  317.         Cflag = Continuity > 0;
  318.         fillrule -= CONTINUITY;
  319.     }
  320.     else
  321.         Cflag = Continuity > 1;
  322.  
  323.     ARGCHECK((fillrule != WINDINGRULE && fillrule != EVENODDRULE),
  324.         "Interior: bad fill rule", NULL, NULL, (1, p,NULL,NULL), struct region *);
  325.  
  326.     if (p->type == TEXTTYPE)
  327. /*             if (fillrule != EVENODDRULE)
  328.                else */
  329.         return ((struct region *)UniquePath(p));
  330.  
  331.     if (p->type == STROKEPATHTYPE)
  332.         if (fillrule == WINDINGRULE)
  333.             return ((struct region *)DoStroke(p));
  334.         else
  335.             p = CoercePath(p);
  336.  
  337.     R = (struct region *)Allocate(sizeof(struct region), &EmptyRegion, 0);
  338.  
  339.     ARGCHECK(!ISPATHANCHOR(p), "Interior:  bad path", p, R, (0,NULL,NULL,NULL), struct region *);
  340.     ARGCHECK((p->type != MOVETYPE), "Interior:  path not closed", p, R, (0,NULL,NULL,NULL), struct region *);
  341.  
  342.  
  343. /* changed definition from !ISPERMANENT to references <= 1 3-26-91 PNM */
  344.     tempflag = (p->references <= 1);    /* only first segment in path is so marked */
  345.     if (!ISPERMANENT(p->flag))
  346.         p->references -= 1;
  347.  
  348.     R->newedgefcn = newfilledge;
  349.  
  350.     /*
  351.      * Believe it or not, "R" is now completely initialized.  We are counting
  352.      * on the copy of template to get other fields the way we want them,
  353.      * namely
  354.      *
  355.      * anchor = NULL
  356.      * xmin, ymin, xmax, ymax, to minimum and maximum values respectively.
  357.      *
  358.      * Anchor = NULL is very
  359.      * important to ChangeDirection.
  360.      * See CD.
  361.      *
  362.      * To minimize problems of "wrapping" in our pel arithmetic, we keep an
  363.      * origin of the region which is the first move.  Hopefully, that keeps
  364.      * numbers within plus or minus 32K pels.
  365.      */
  366.     R->origin.x = 0 /*TOFRACTPEL(NEARESTPEL(p->dest.x))*/ ;
  367.     R->origin.y = 0 /*TOFRACTPEL(NEARESTPEL(p->dest.y))*/ ;
  368.     lastx = -R->origin.x;
  369.     lasty = -R->origin.y;
  370.  
  371.     /*
  372.      * ChangeDirection initializes other important fields in R, such as
  373.      * lastdy, edge, edgeYstop, edgexmin, and edgexmax.  The first segment
  374.      * is a MOVETYPE, so it will be called first.
  375.      */
  376.  
  377.     /*
  378.      * The hints data structure must be initialized once for each path.
  379.      */
  380.     if (ProcessHints)
  381.         InitHints();    /* initialize hint data structure */
  382.  
  383.     while (p != NULL)
  384.     {
  385.  
  386.         x = lastx + p->dest.x;
  387.         y = lasty + p->dest.y;
  388.  
  389.         IfTrace2((HintDebug > 0), "Ending point = (%p,%p)\n", x, y);
  390.  
  391.         nextP = p->link;
  392.  
  393.         /*
  394.          * Here we start the hints processing by initializing the hint value to
  395.          * zero.  If ProcessHints is FALSE, the value will remain zero.
  396.          * Otherwise, hint accumulates the computed hint values.
  397.          */
  398.         hint.x = hint.y = 0;
  399.  
  400.         /*
  401.          * If we are processing hints, and this is a MOVE segment (other than
  402.          * the first on the path), we need to close (reverse) any open hints.
  403.          */
  404.         if (ProcessHints)
  405.             if ((p->type == MOVETYPE) && (p->last == NULL))
  406.             {
  407.                 CloseHints(&hint);
  408.                 IfTrace2((HintDebug > 0), "Closed point= (%p,%p)\n",
  409.                      x + hint.x, y + hint.y);
  410.             }
  411.  
  412.         /*
  413.          * Next we run through all the hint segments (if any) attached to this
  414.          * segment.  If ProcessHints is TRUE, we will accumulate computed hint
  415.          * values.  In either case, nextP will be advanced to the first non-HINT
  416.          * segment (or NULL), and each hint segment will be freed if necessary.
  417.          */
  418.         while ((nextP != NULL) && (nextP->type == HINTTYPE))
  419.         {
  420.             if (ProcessHints)
  421.                 ProcessHint(nextP, x + hint.x, y + hint.y, &hint);
  422.  
  423.             {
  424.                 register struct segment *saveP = nextP;
  425.  
  426.                 nextP = nextP->link;
  427.                 if (tempflag)
  428.                     Free(saveP);
  429.             }
  430.         }
  431.  
  432.         /*
  433.          * We now apply the full hint value to the ending point of the path segment.
  434.          */
  435.         x += hint.x;
  436.         y += hint.y;
  437.  
  438.         IfTrace2((HintDebug > 0), "Hinted ending point = (%p,%p)\n", x, y);
  439.  
  440.         switch (p->type)
  441.         {
  442.  
  443.         case LINETYPE:
  444.             StepLine(R, lastx, lasty, x, y);
  445.             break;
  446.  
  447.         case CONICTYPE:
  448.             {
  449.             /*
  450.              * For a conic curve, we apply half the hint value to the conic midpoint.
  451.              */
  452.             }
  453.             break;
  454.  
  455.         case BEZIERTYPE:
  456.             {
  457.                 register struct beziersegment *bp = (struct beziersegment *)p;
  458.  
  459.             /*
  460.              * For a Bezier curve, we apply the full hint value to the Bezier C point.
  461.              */
  462.                 StepBezier(R, lastx, lasty,
  463.                        lastx + bp->B.x, lasty + bp->B.y,
  464.                        lastx + bp->C.x + hint.x,
  465.                        lasty + bp->C.y + hint.y,
  466.                        x, y);
  467.             }
  468.             break;
  469.  
  470.         case MOVETYPE:
  471.             /*
  472.              * At this point we have encountered a MOVE segment.  This breaks the
  473.              * path, making it disjoint.
  474.              */
  475.             if (p->last == NULL)    /* i.e., not first in path */
  476.                 ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
  477.  
  478.             ChangeDirection(CD_FIRST, R, x, y, (fractpel) 0);
  479.  
  480.             /*
  481.              * We'll just double check for closure here.  We forgive an appended
  482.              * MOVETYPE at the end of the path, if it isn't closed:
  483.              */
  484.             if (!ISCLOSED(p->flag) && p->link != NULL)
  485.                 return ((struct region *)ArgErr("Fill: sub-path not closed", p, NULL));
  486.             break;
  487.  
  488.         default:
  489.             t1_abort("Interior: path type error");
  490.         }
  491.  
  492.         /*
  493.          * We're done with this segment.  Advance to the next path segment in
  494.          * the list, freeing this one if necessary:
  495.          */
  496.         lastx = x;
  497.         lasty = y;
  498.  
  499.         if (tempflag)
  500.             Free(p);
  501.         p = nextP;
  502.     }
  503.     ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
  504.     R->ending.x = lastx;
  505.     R->ending.y = lasty;
  506.  
  507.     /*
  508.      * Finally, clean up the region's based on the user's 'fillrule' request:
  509.      */
  510.     if (Cflag)
  511.         ApplyContinuity(R);
  512.     if (fillrule == WINDINGRULE)
  513.         Unwind(R->anchor);
  514.     return (R);
  515. }
  516.  
  517.  
  518. /*
  519.  * Unwind() - Discards Edges That Fail the Winding Rule Test
  520.  *
  521.  * The winding rule says that upward going edges should be paired with
  522.  * downward going edges only, and vice versa.  So, if two upward edges
  523.  * or two downward edges are nominally left/right pairs, Unwind() should
  524.  * discard the second one.  Everything should balance; we should discard
  525.  * an even number of edges; of course, we abort if we don't.
  526.  */
  527. static void Unwind(
  528.         struct edgelist *area)        /* input area modified in place */
  529. {
  530.     struct edgelist *last, *next;    /* struct before and after current one */
  531.     int y;                            /* ymin of current swath */
  532.     int count, newcount;            /* winding count registers */
  533.  
  534.     IfTrace1((RegionDebug > 0), "...Unwind(%z)\n", area);
  535.  
  536.     while (VALIDEDGE(area))
  537.     {
  538.  
  539.         count = 0;
  540.         y = area->ymin;
  541.  
  542.         do
  543.         {
  544.             next = area->link;
  545.  
  546.             if (ISDOWN(area->flag))
  547.                 newcount = count + 1;
  548.             else
  549.                 newcount = count - 1;
  550.  
  551.             if (count == 0 || newcount == 0)
  552.                 last = area;
  553.             else
  554.                 discard(last, next);
  555.  
  556.             count = newcount;
  557.             area = next;
  558.  
  559.         }
  560.         while (area != NULL && area->ymin == y);
  561.  
  562.         if (count != 0)
  563.             t1_abort("Unwind:  uneven edges");
  564.     }
  565. }
  566.  
  567.  
  568. /*
  569.  * "workedge" Array
  570.  *
  571.  * This is a statically allocated array where edges are built
  572.  * before being copied into more permanent storage by NewEdge().
  573.  */
  574.  
  575. #ifndef   MAXEDGE
  576. #define   MAXEDGE     1000
  577. #endif
  578.  
  579. static pel workedge[MAXEDGE];
  580. static pel *currentworkarea = workedge;
  581. static pel currentsize = MAXEDGE;
  582.  
  583.  
  584. /*
  585.  * ChangeDirection() - Called When Y Direction Changes
  586.  *
  587.  * The rasterizing routines call this entry point when they detect
  588.  * a change in Y.  We then build the current edge and sort it into
  589.  * emerging edgelist at 'anchor' by calling whatever "newedgefcn"
  590.  * is appropriate.
  591.  */
  592. void ChangeDirection(
  593.         int type,            /* CD_FIRST, CD_CONTINUE, or CD_LAST */
  594.         struct region *R,        /* region in which we are changing direction */
  595.         fractpel x, fractpel y,        /* current beginning x,y */
  596.         fractpel dy)            /* direction and magnitude of change in y */
  597. {
  598.     fractpel ymin, ymax;            /* minimum and maximum Y since last call */
  599.     fractpel x_at_ymin, x_at_ymax;        /* their respective X's */
  600.     pel iy;                    /* nearest integer pel to 'y' */
  601.     pel idy;                /* nearest integer pel to 'dy' */
  602.     int ydiff;                /* allowed Y difference in 'currentworkarea' */
  603.  
  604.     IfTrace4((RegionDebug > 0), "Change Y direction (%d) from (%p,%p), dy=%p\n",
  605.          (long)type, x, y, dy);
  606.  
  607.     if (type != CD_FIRST)
  608.     {
  609.  
  610.         if (R->lastdy > 0)
  611.         {
  612.             ymin = R->firsty;
  613.             x_at_ymin = R->firstx;
  614.             ymax = y;
  615.             x_at_ymax = x;
  616.         }
  617.         else
  618.         {
  619.             ymin = y;
  620.             x_at_ymin = x;
  621.             ymax = R->firsty;
  622.             x_at_ymax = R->firstx;
  623.         }
  624.  
  625.         if (ymax < ymin)
  626.             t1_abort("negative sized edge?");
  627.  
  628.  
  629. //        (*R->newedgefcn) (R, R->edgexmin, R->edgexmax, ymin, ymax,
  630. //                  R->lastdy > 0, x_at_ymin, x_at_ymax);
  631.         (*R->newedgefcn) (R, R->edgexmin, R->edgexmax, ymin, ymax,
  632.                   R->lastdy > 0);
  633.  
  634.     }
  635.  
  636.     R->firsty = y;
  637.     R->firstx = x;
  638.     R->lastdy = dy;
  639.  
  640.     iy = NEARESTPEL(y);
  641.     idy = NEARESTPEL(dy);
  642.     if (currentworkarea != workedge && idy < MAXEDGE && idy > -MAXEDGE)
  643.     {
  644.         NonObjectFree(currentworkarea);
  645.         currentworkarea = workedge;
  646.         currentsize = MAXEDGE;
  647.     }
  648.     ydiff = currentsize - 1;
  649.     if (dy > 0)
  650.     {
  651.         R->edge = ¤tworkarea[-iy];
  652.         R->edgeYstop = TOFRACTPEL(ydiff + iy) + FPHALF;
  653.     }
  654.     else
  655.     {
  656.         R->edge = ¤tworkarea[ydiff - iy];
  657.         R->edgeYstop = TOFRACTPEL(iy - ydiff) - FPHALF;
  658.     }
  659.     R->edgexmax = R->edgexmin = x;
  660.  
  661.     /*
  662.      * If this is the end of a subpath, we complete the subpath circular
  663.      * chain:
  664.      */
  665.     if (type == CD_LAST && R->lastedge != NULL)
  666.     {
  667.         register struct edgelist *e = R->firstedge;
  668.  
  669.         while (e->subpath != NULL)
  670.             e = e->subpath;
  671.         e->subpath = R->lastedge;
  672.         R->lastedge = R->firstedge = NULL;
  673.     }
  674. }
  675.  
  676.  
  677. /*
  678.  * newfilledge() - Called When We Have a New Edge While Filling
  679.  *
  680.  * This is the prototypical "newedge" function passed to "Rasterize" and
  681.  * stored in "newedgefcn" in the region being built.
  682.  *
  683.  * If the edge is non-null, we sort it onto the list of edges we are
  684.  * building at "anchor".
  685.  *
  686.  * This function also has to keep the bounding box of the region
  687.  * up to date.
  688.  */
  689. static void newfilledge(
  690.         struct region *R,        /* region being built */
  691.         fractpel xmin,
  692.         fractpel xmax,            /* X range of this edge */
  693.         fractpel ymin,
  694.         fractpel ymax,            /* Y range of this edge */
  695.         int isdown)            /* flag:  TRUE means edge goes down, else up */
  696. {
  697.     pel pelxmin, pelymin, pelxmax, pelymax;    /* pel versions of bounds */
  698.     struct edgelist *edge;            /* newly created edge */
  699.  
  700.     pelymin = NEARESTPEL(ymin);
  701.     pelymax = NEARESTPEL(ymax);
  702.     if (pelymin == pelymax)
  703.         return;
  704.  
  705.     pelxmin = NEARESTPEL(xmin);
  706.     pelxmax = NEARESTPEL(xmax);
  707.  
  708.     if (pelxmin < R->xmin)
  709.         R->xmin = pelxmin;
  710.     if (pelxmax > R->xmax)
  711.         R->xmax = pelxmax;
  712.     if (pelymin < R->ymin)
  713.         R->ymin = pelymin;
  714.     if (pelymax > R->ymax)
  715.         R->ymax = pelymax;
  716.  
  717.     edge = NewEdge(pelxmin, pelxmax, pelymin, pelymax, &R->edge[pelymin], isdown);
  718.     edge->subpath = R->lastedge;
  719.     R->lastedge = edge;
  720.     if (R->firstedge == NULL)
  721.         R->firstedge = edge;
  722.  
  723.     R->anchor = SortSwath(R->anchor, edge, swathxsort);
  724. }
  725.  
  726.  
  727. /*
  728.  * Sorting Edges
  729.  *
  730.  * SortSwath() - Vertically Sort an Edge into a Region
  731.  *
  732.  * This routine sorts an edge or a pair of edges into a growing region,
  733.  * so that the region maintains its top-to-bottom, left-to-right form.
  734.  * The rules for sorting horizontally may vary depending on what you
  735.  * are doing, but the rules for vertical sorting are always the same.
  736.  * This routine is passed an argument that is a function that will
  737.  * perform the horizontal sort on demand (for example, swathxsort() or
  738.  * SwathUnion()).
  739.  *
  740.  * This is a recursive routine.  A new edge (or edge pair) may overlap
  741.  * the list I am building in strange and wonderful ways.  Edges may
  742.  * cross.  When this happens, my strategy is to split the incoming edge
  743.  * (or the growing list) in two at that point, execute the actual sort on
  744.  * the top part of the split, and recursively call myself to figure out
  745.  * exactly where the bottom part belongs.
  746.  */
  747. #define   TOP(e)      ((e)->ymin)    /* the top of an edge (for readability    */
  748. #define   BOTTOM(e)   ((e)->ymax)    /* the bottom of an edge (for readability */
  749.  
  750. struct edgelist *SortSwath(
  751.         struct edgelist *anchor,            /* list being built */
  752.         struct edgelist *edge,                /* incoming edge or pair of edges */
  753.         struct edgelist *(*swathfcn) (struct edgelist *, struct edgelist *))    /* horizontal sorter */
  754. {
  755.     struct edgelist *before, *after;
  756.     struct edgelist base;
  757.  
  758.     if (RegionDebug > 0)
  759.     {
  760.         if (RegionDebug > 2)
  761.         {
  762.             IfTrace3(TRUE, "SortSwath(anchor=%z, edge=%z, fcn=%x)\n",
  763.                  anchor, edge, swathfcn);
  764.         }
  765.         else
  766.         {
  767.             IfTrace3(TRUE, "SortSwath(anchor=%x, edge=%x, fcn=%x)\n",
  768.                  anchor, edge, swathfcn);
  769.         }
  770.     }
  771.     if (anchor == NULL)
  772.         return (edge);
  773.  
  774.     before = &base;
  775.     before->ymin = before->ymax = MINPEL;
  776.     before->link = after = anchor;
  777.  
  778.     /*
  779.      * If the incoming edge is above the current list, we connect the current
  780.      * list to the bottom of the incoming edge.  One slight complication is
  781.      * if the incoming edge overlaps into the current list.  Then, we
  782.      * first split the incoming edge in two at the point of overlap and recursively
  783.      * call ourselves to sort the bottom of the split into the current list:
  784.      */
  785.     if (TOP(edge) < TOP(after))
  786.     {
  787.         if (BOTTOM(edge) > TOP(after))
  788.         {
  789.  
  790.             after = SortSwath(after, splitedge(edge, TOP(after)), swathfcn);
  791.         }
  792.         vertjoin(edge, after);
  793.         return (edge);
  794.     }
  795.  
  796.     /*
  797.      * At this point the top of edge is not higher than the top of the list,
  798.      * which we keep in 'after'.  We move the 'after' point down the list,
  799.      * until the top of the edge occurs in the swath beginning with 'after'.
  800.      *
  801.      * If the bottom of 'after' is below the bottom of the edge, we have to
  802.      * split the 'after' swath into two parts, at the bottom of the edge.
  803.      * If the bottom of 'after' is above the bottom of the swath,
  804.      */
  805.     while (VALIDEDGE(after))
  806.     {
  807.  
  808.         if (TOP(after) == TOP(edge))
  809.         {
  810.             if (BOTTOM(after) > BOTTOM(edge))
  811.                 vertjoin(after, splitedge(after, BOTTOM(edge)));
  812.             else if (BOTTOM(after) < BOTTOM(edge))
  813.             {
  814.                 after = SortSwath(after,
  815.                   splitedge(edge, BOTTOM(after)), swathfcn);
  816.             }
  817.             break;
  818.         }
  819.         else if (TOP(after) > TOP(edge))
  820.         {
  821.             IfTrace0((BOTTOM(edge) < TOP(after) && RegionDebug > 0),
  822.                  "SortSwath:  disjoint edges\n");
  823.             if (BOTTOM(edge) > TOP(after))
  824.             {
  825.                 after = SortSwath(after,
  826.                      splitedge(edge, TOP(after)), swathfcn);
  827.             }
  828.             break;
  829.         }
  830.         else if (BOTTOM(after) > TOP(edge))
  831.             vertjoin(after, splitedge(after, TOP(edge)));
  832.  
  833.         before = after;
  834.         after = after->link;
  835.     }
  836.  
  837.     /*
  838.      * At this point 'edge' exactly corresponds in height to the current
  839.      * swath pointed to by 'after'.
  840.      */
  841.     if (after != NULL && TOP(after) == TOP(edge))
  842.     {
  843.         before = (*swathfcn) (before, edge);
  844.         after = before->link;
  845.     }
  846.  
  847.     /*
  848.      * At this point 'after' contains all the edges after 'edge', and 'before'
  849.      * contains all the edges before.  Whew!  A simple matter now of adding
  850.      * 'edge' to the linked list in its rightful place:
  851.      */
  852.     before->link = edge;
  853.     if (RegionDebug > 1)
  854.     {
  855.         IfTrace3(TRUE, "SortSwath:  in between %x and %x are %x",
  856.              before, after, edge);
  857.         while (edge->link != NULL)
  858.         {
  859.             edge = edge->link;
  860.             IfTrace1(TRUE, " and %x", edge);
  861.         }
  862.         IfTrace0(TRUE, "\n");
  863.     }
  864.     else
  865.         for (; edge->link != NULL; edge = edge->link)
  866.         {;
  867.         }
  868.  
  869.     edge->link = after;
  870.     return (base.link);
  871. }
  872.  
  873.  
  874. /*
  875.  * splitedge() - Split an Edge or Swath in Two at a Given Y Value
  876.  *
  877.  * This function returns the edge or swath beginning at the Y value, and
  878.  * is guaranteed not to change the address of the old swath while splitting
  879.  * it.
  880.  */
  881. static struct edgelist *splitedge(
  882.         struct edgelist *list,    /* area to split */
  883.         pel y)            /* Y value to split list at */
  884. {
  885.     struct edgelist *new;        /* anchor for newly built list */
  886.     struct edgelist *last;        /* end of newly built list */
  887.     struct edgelist *r;        /* temp pointer to new structure */
  888.     struct edgelist *lastlist;    /* temp pointer to last 'list' value */
  889.  
  890.     IfTrace2((RegionDebug > 1), "splitedge of %x at %d ", list, (long)y);
  891.  
  892.     lastlist = new = NULL;
  893.  
  894.     while (list != NULL)
  895.     {
  896.         if (y < list->ymin)
  897.             break;
  898.         if (y >= list->ymax)
  899.             t1_abort("splitedge: above top of list");
  900.         if (y == list->ymin)
  901.             t1_abort("splitedge: would be null");
  902.  
  903.         r = (struct edgelist *)Allocate(sizeof(struct edgelist), list, 0);
  904.  
  905.         /*
  906.          * At this point 'r' points to a copy of the single structure at 'list'.
  907.          * We will make 'r' be the new split 'edgelist'--the lower half.
  908.          * We don't bother to correct 'xmin' and 'xmax', we'll take the
  909.          * the pessimistic answer that results from using the old values.
  910.          */
  911.         r->ymin = y;
  912.         r->xvalues = list->xvalues + (y - list->ymin);
  913.  
  914.         /*
  915.          * Note that we do not need to allocate new memory for the X values,
  916.          * they can remain with the old "edgelist" structure.  We do have to
  917.          * update that old structure so it is not as high:
  918.          */
  919.         list->ymax = y;
  920.  
  921.         /*
  922.          * Insert 'r' in the subpath chain:
  923.          */
  924.         r->subpath = list->subpath;
  925.         list->subpath = r;
  926.  
  927.         /*
  928.          * Now attach 'r' to the list we are building at 'new', and advance
  929.          * 'list' to point to the next element in the old list:
  930.          */
  931.         if (new == NULL)
  932.             new = r;
  933.         else
  934.             last->link = r;
  935.         last = r;
  936.         lastlist = list;
  937.         list = list->link;
  938.     }
  939.  
  940.     /*
  941.      * At this point we have a new list built at 'new'.  We break the old
  942.      * list at 'lastlist', and add the broken off part to the end of 'new'.
  943.      * Then, we return the caller a pointer to 'new':
  944.      */
  945.     if (new == NULL)
  946.         t1_abort("null splitedge");
  947.     lastlist->link = NULL;
  948.     last->link = list;
  949.     IfTrace1((RegionDebug > 1), "yields %x\n", new);
  950.     return (new);
  951. }
  952.  
  953.  
  954. /*
  955.  * vertjoin() - Join Two Disjoint Edge Lists Vertically
  956.  *
  957.  * The two edges must be disjoint vertically.
  958.  */
  959. static void vertjoin(struct edgelist *top, struct edgelist *bottom)
  960. {
  961.     if (BOTTOM(top) > TOP(bottom))
  962.         t1_abort("vertjoin not disjoint");
  963.  
  964.     for (; top->link != NULL; top = top->link)
  965.     {;
  966.     }
  967.  
  968.     top->link = bottom;
  969.     return;
  970. }
  971.  
  972.  
  973. /*
  974.  * swathxsort() - Sorting by X Values
  975.  *
  976.  * We need to sort 'edge' into its rightful
  977.  * place in the swath by X value, taking care that we do not accidentally
  978.  * advance to the next swath while searching for the correct X value.  Like
  979.  * all swath functions, this function returns a pointer to the edge
  980.  * BEFORE the given edge in the sort.
  981.  */
  982. static struct edgelist *swathxsort(
  983.         struct edgelist *before0,     /* edge before this swath */
  984.         struct edgelist *edge)        /* input edge */
  985. {
  986.     struct edgelist *before;
  987.     struct edgelist *after;
  988.     pel y;
  989.  
  990.     before = before0;
  991.     after = before->link;
  992.  
  993.     while (after != NULL && TOP(after) == TOP(edge))
  994.     {
  995.  
  996.         register pel *x1, *x2;
  997.  
  998.         y = TOP(edge);
  999.         x1 = after->xvalues;
  1000.         x2 = edge->xvalues;
  1001.  
  1002.         while (y < BOTTOM(edge) && *x1 == *x2)
  1003.         {
  1004.             x1++;
  1005.             x2++;
  1006.             y++;
  1007.         }
  1008.         if (y >= BOTTOM(edge))
  1009.         {
  1010.             edge->flag |= ISAMBIGUOUS(ON);
  1011.             after->flag |= ISAMBIGUOUS(ON);
  1012.             break;
  1013.         }
  1014.  
  1015.         if (*x1 >= *x2)
  1016.             break;
  1017.  
  1018.         before = after;
  1019.         after = after->link;
  1020.     }
  1021.  
  1022.     /*
  1023.      * At this point, 'edge' is between 'before' and 'after'.  If 'edge' didn't
  1024.      * cross either of those other edges, we would be done.  We check for
  1025.      * crossing.  If it does cross, we split the problem up by calling SortSwath
  1026.      * recursively with the part of the edge that is below the crossing point:
  1027.      */
  1028.     {
  1029.         register int h0, h;            /* height of edge--number of scans */
  1030.  
  1031.         h0 = h = BOTTOM(edge) - y;
  1032.         y -= TOP(edge);
  1033.  
  1034.         if (h0 <= 0)
  1035.         {
  1036.             IfTrace0((RegionDebug > 0), "swathxsort: exactly equal edges\n");
  1037.             return (before);
  1038.         }
  1039.  
  1040.         if (TOP(before) == TOP(edge))
  1041.             h -= crosses(h, &before->xvalues[y], &edge->xvalues[y]);
  1042.         if (after != NULL && TOP(after) == TOP(edge))
  1043.             h -= crosses(h, &edge->xvalues[y], &after->xvalues[y]);
  1044.  
  1045.         if (h < h0)
  1046.         {
  1047.             SortSwath(before0->link,
  1048.                   splitedge(edge, TOP(edge) + y + h),
  1049.                   swathxsort);
  1050.         }
  1051.     }
  1052.  
  1053.     return (before);
  1054. }
  1055.  
  1056.  
  1057. /*
  1058.  * SwathUnion() - Union Two Edges by X Value
  1059.  *
  1060.  * We have a left and right edge that must be unioned into a growing
  1061.  * swath.  If they are totally disjoint, they are just added in.  The
  1062.  * fun comes in they overlap the existing edges.  Then some edges
  1063.  * will disappear.
  1064.  */
  1065. struct edgelist *SwathUnion(
  1066.         struct edgelist *before0,     /* edge before the swath */
  1067.         struct edgelist *edge)        /* list of two edges to be unioned */
  1068. {
  1069.     int h;                    /* saves height of edge */
  1070.     struct edgelist *rightedge;        /* saves right edge of 'edge' */
  1071.     struct edgelist *before, *after;     /* edge before and after */
  1072.     int h0;                    /* saves initial height */
  1073.  
  1074.     IfTrace2((RegionDebug > 1), "SwathUnion entered, before=%x, edge=%x\n",
  1075.          before0, edge);
  1076.  
  1077.     h0 = h = edge->ymax - edge->ymin;
  1078.     if (h <= 0)
  1079.         t1_abort("SwathUnion:  0 height swath?");
  1080.  
  1081.     before = before0;
  1082.     after = before->link;
  1083.  
  1084.     while (after != NULL && TOP(after) == TOP(edge))
  1085.     {
  1086.         register struct edgelist *right;
  1087.  
  1088.         right = after->link;
  1089.         if (right->xvalues[0] >= edge->xvalues[0])
  1090.             break;
  1091.         before = right;
  1092.         after = before->link;
  1093.     }
  1094.  
  1095.     /*
  1096.      * This is the picture at this point.  'L' indicates a left hand edge,
  1097.      * 'R' indicates the right hand edge.
  1098.      * '<--->' indicates the degree of uncertainty as to its placement
  1099.      * relative to other edges:
  1100.      *
  1101.      *    before           after
  1102.      *      R            <---L---->  R             L   R    L   R
  1103.      *               <---L--->  <------R-------------------------->
  1104.      *                  edge
  1105.      *
  1106.      * In case the left of 'edge' touches 'before', we need to reduce
  1107.      * the height by that amount.
  1108.      */
  1109.     if (TOP(before) == TOP(edge))
  1110.         h -= touches(h, before->xvalues, edge->xvalues);
  1111.  
  1112.     rightedge = edge->link;
  1113.  
  1114.     if (after == NULL || TOP(after) != TOP(edge) ||
  1115.         after->xvalues[0] > rightedge->xvalues[0])
  1116.     {
  1117.         IfTrace2((RegionDebug > 1),
  1118.              "SwathUnion starts disjoint: before=%x after=%x\n",
  1119.              before, after);
  1120.  
  1121.         /*
  1122.          * On this side of the the above 'if', the new edge is disjoint from the
  1123.          * existing edges in the swath.  This is the picture:
  1124.          *
  1125.          *    before           after
  1126.          *      R                L    R     L   R    L   R
  1127.          *               L    R
  1128.          *              edge
  1129.          *
  1130.          * We will verify it remains disjoint for the entire height.  If the
  1131.          * situation changes somewhere down the edge, we split the edge at that
  1132.          * point and recursively call ourselves (through 'SortSwath') to figure
  1133.          * out the new situation:
  1134.          */
  1135.         if (after != NULL && TOP(after) == TOP(edge))
  1136.             h -= touches(h, rightedge->xvalues, after->xvalues);
  1137.         if (h < h0)
  1138.             SortSwath(before0->link, splitedge(edge, edge->ymin + h), t1_SwathUnion);
  1139.  
  1140.         /* go to "return" this edge pair; it is totally disjoint */
  1141.     }
  1142.     else
  1143.     {
  1144.         /*
  1145.          * At this point, at the 'else', we know that the
  1146.          * new edge overlaps one or more pairs in the existing swath.  Here is
  1147.          * a picture of our knowledge and uncertainties:
  1148.          *
  1149.          *    before       after
  1150.          *      R            L        R     L   R    L   R
  1151.          *             <---L--->   <---R------------------->
  1152.          *                edge
  1153.          *
  1154.          * We need to move 'after' along until it is to the right of the
  1155.          * right of 'edge'.  ('After' should always point to a left edge of a pair:)
  1156.          */
  1157.         register struct edgelist *left;    /* variable to keep left edge in */
  1158.  
  1159.         do
  1160.         {
  1161.             left = after;
  1162.             after = (after->link)->link;
  1163.  
  1164.         }
  1165.         while (after != NULL && TOP(after) == TOP(edge)
  1166.                && after->xvalues[0] <= rightedge->xvalues[0]);
  1167.  
  1168.         /*
  1169.          * At this point this is the picture:
  1170.          *
  1171.          *    before                 left        after
  1172.          *      R            L    R   L      R     L   R
  1173.          *             <---L--->        <---R--->
  1174.          *                edge
  1175.          *
  1176.          * We need to verify that the situation stays like this all the way
  1177.          * down the edge.  Again, if the
  1178.          * situation changes somewhere down the edge, we split the edge at that
  1179.          * point and recursively call ourselves (through 'SortSwath') to figure
  1180.          * out the new situation:
  1181.          */
  1182.         h -= crosses(h, left->xvalues, rightedge->xvalues);
  1183.         h -= crosses(h, edge->xvalues, ((before->link)->link)->xvalues);
  1184.  
  1185.         if (after != NULL && TOP(after) == TOP(edge))
  1186.  
  1187.             h -= touches(h, rightedge->xvalues, after->xvalues);
  1188.  
  1189.         IfTrace3((RegionDebug > 1),
  1190.           "SwathUnion is overlapped until %d: before=%x after=%x\n",
  1191.              (long)TOP(edge) + h, before, after);
  1192.  
  1193.         /*
  1194.          * OK, if we touched either of our neighbors we need to split at that point
  1195.          * and recursively sort the split edge onto the list.  One tricky part
  1196.          * is that when we recursively sort, 'after' will change if it was not
  1197.          * in our current swath:
  1198.          */
  1199.         if (h < h0)
  1200.         {
  1201.             SortSwath(before0->link,
  1202.                   splitedge(edge, edge->ymin + h),
  1203.                   t1_SwathUnion);
  1204.  
  1205.             if (after == NULL || TOP(after) != TOP(edge))
  1206.                 for (after = before0->link;
  1207.                      TOP(after) == TOP(edge);
  1208.                      after = after->link)
  1209.                 {;
  1210.                 }
  1211.         }
  1212.  
  1213.         /*
  1214.          * Now we need to augment 'edge' by the left and right of the overlapped
  1215.          * swath, and to discard all edges between before and after, because they
  1216.          * were overlapped and have been combined with the new incoming 'edge':
  1217.          */
  1218.         edge->xmin = MIN(edge->xmin, (before->link)->xmin);
  1219.         edge->xmax = MIN(edge->xmax, (before->link)->xmax);
  1220.         edgemin(h, edge->xvalues, (before->link)->xvalues);
  1221.         rightedge->xmin = MAX(rightedge->xmin, (left->link)->xmin);
  1222.         rightedge->xmax = MAX(rightedge->xmax, (left->link)->xmax);
  1223.         edgemax(h, rightedge->xvalues, (left->link)->xvalues);
  1224.         discard(before, after);
  1225.     }
  1226.     return (before);
  1227. }
  1228.  
  1229.  
  1230. /*
  1231.  * swathrightmost() - Simply Sorts New Edge to Rightmost of Swath
  1232.  *
  1233.  * Like all swath functions, this function returns a pointer to the edge
  1234.  * BEFORE the given edge in the sort.
  1235.  */
  1236. static struct edgelist *swathrightmost(
  1237.         struct edgelist *before,/* edge before this swath */
  1238.         struct edgelist *edge)    /* input edge */
  1239. {
  1240.     struct edgelist *after;
  1241.  
  1242.     after = before->link;
  1243.  
  1244.     while (after != NULL && TOP(after) == TOP(edge))
  1245.     {
  1246.         before = after;
  1247.         after = after->link;
  1248.     }
  1249.  
  1250.     return (before);
  1251.  
  1252. }
  1253.  
  1254.  
  1255. /*
  1256.  * touches() - Returns the Remaining Height When Two Edges Touch
  1257.  *
  1258.  * So, it will return 0 if they never touch.  Allows incredibly(?) mnemonic
  1259.  * if (touches(...)) construct.
  1260.  */
  1261. static int touches(int h, pel *left, pel *right)
  1262. {
  1263.     for (; h > 0; h--)
  1264.         if (*left++ >= *right++)
  1265.             break;
  1266.     return (h);
  1267. }
  1268.  
  1269.  
  1270. /*
  1271.  * crosses() - Returns the Remaining Height When Two Edges Cross
  1272.  *
  1273.  * So, it will return 0 if they never cross.
  1274.  */
  1275. static int crosses(int h, pel *left, pel *right)
  1276. {
  1277.     for (; h > 0; h--)
  1278.         if (*left++ > *right++)
  1279.             break;
  1280.     return (h);
  1281. }
  1282.  
  1283.  
  1284. /*
  1285.  * cedgemin() - Stores the Mininum of an Edge and an X Value
  1286.  */
  1287. static void cedgemin(int h, pel *e1, pel x)
  1288. {
  1289.     for (; --h >= 0; e1++)
  1290.         if (*e1 > x)
  1291.             *e1 = x;
  1292. }
  1293.  
  1294.  
  1295. /*
  1296.  * cedgemax() - Stores the Maximum of an Edge and an X Value
  1297.  */
  1298. static void cedgemax(int h, pel *e1, pel x)
  1299. {
  1300.     for (; --h >= 0; e1++)
  1301.         if (*e1 < x)
  1302.             *e1 = x;
  1303. }
  1304.  
  1305.  
  1306. /*
  1307.  * edgemin() - Stores the Mininum of Two Edges in First Edge
  1308.  */
  1309. static void edgemin(int h, pel *e1, pel *e2)
  1310. {
  1311.     for (; --h >= 0; e1++, e2++)
  1312.         if (*e1 > *e2)
  1313.             *e1 = *e2;
  1314. }
  1315.  
  1316.  
  1317. /*
  1318.  * edgemax() - Stores the Maximum of Two Edges in First Edge
  1319.  */
  1320. static void edgemax(int h, pel *e1, pel *e2)
  1321. {
  1322.     for (; --h >= 0; e1++, e2++)
  1323.         if (*e1 < *e2)
  1324.             *e1 = *e2;
  1325. }
  1326.  
  1327.  
  1328. /*
  1329.  * discard() - Discard All Edges Between Two Edges
  1330.  *
  1331.  * At first glance it would seem that we could discard an edgelist
  1332.  * structure merely by unlinking it from the list and freeing it.  You are
  1333.  * wrong, region-breath!  For performance, the X values associated with an
  1334.  * edge are allocated contiguously with it.  So, we free the X values when
  1335.  * we free a structure.  However, once an edge has been split, we are no
  1336.  * longer sure which control block actually is part of the memory block
  1337.  * that contains the edges.  Rather than trying to decide, we play it safe
  1338.  * and never free part of a region.
  1339.  *
  1340.  * So, to mark a 'edgelist' structure as discarded, we move it to the end
  1341.  * of the list and set ymin=ymax.
  1342.  */
  1343. static void discard(struct edgelist *left, struct edgelist *right)
  1344. {
  1345.     struct edgelist *beg, *end, *p;
  1346.  
  1347.     IfTrace2((RegionDebug > 0), "discard:  l=%x, r=%x\n", left, right);
  1348.  
  1349.     beg = left->link;
  1350.     if (beg == right)
  1351.         return;
  1352.  
  1353.     for (p = beg; p != right; p = p->link)
  1354.     {
  1355.         if (p->link == NULL && right != NULL)
  1356.             t1_abort("discard():  ran off end");
  1357.         IfTrace1((RegionDebug > 0), "discarding %x\n", p);
  1358.         p->ymin = p->ymax = 32767;
  1359.         end = p;
  1360.     }
  1361.  
  1362.     /*
  1363.      * now put the chain beg/end at the end of right, if it is not
  1364.      * already there:
  1365.      */
  1366.     if (right != NULL)
  1367.     {
  1368.         left->link = right;
  1369.         while (right->link != NULL)
  1370.             right = right->link;
  1371.         right->link = beg;
  1372.     }
  1373.     end->link = NULL;
  1374. }
  1375.  
  1376.  
  1377. /*
  1378.  * Changing the Representation of Regions
  1379.  *
  1380.  * For convenience and/or performance, we sometimes like to change the way
  1381.  * regions are represented.  This does not change the object itself, just
  1382.  * the representation, so these transformations can be made on a permanent
  1383.  * region.
  1384.  */
  1385. void MoveEdges(
  1386.         struct region *R,        /* region to modify */
  1387.         fractpel dx,
  1388.         fractpel dy)            /* delta X and Y to move edge list by */
  1389. {
  1390.     struct edgelist *edge;        /* for looping through edges */
  1391.  
  1392.     R->origin.x += dx;
  1393.     R->origin.y += dy;
  1394.     R->ending.x += dx;
  1395.     R->ending.y += dy;
  1396.     if (R->thresholded != NULL)
  1397.     {
  1398.         R->thresholded->origin.x -= dx;
  1399.         R->thresholded->origin.y -= dy;
  1400.     }
  1401.  
  1402.     /*
  1403.      * From now on we will deal with dx and dy as integer pel values:
  1404.      */
  1405.     dx = NEARESTPEL(dx);
  1406.     dy = NEARESTPEL(dy);
  1407.     if (dx == 0 && dy == 0)
  1408.         return;
  1409.  
  1410.     R->xmin += dx;
  1411.     R->xmax += dx;
  1412.     R->ymin += dy;
  1413.     R->ymax += dy;
  1414.  
  1415.     for (edge = R->anchor; VALIDEDGE(edge); edge = edge->link)
  1416.     {
  1417.         edge->ymin += dy;
  1418.         edge->ymax += dy;
  1419.         if (dx != 0)
  1420.         {
  1421.             register int h;        /* loop index; height of edge */
  1422.             register pel *Xp;    /* loop pointer to X values */
  1423.  
  1424.             edge->xmin += dx;
  1425.             edge->xmax += dx;
  1426.             for (Xp = edge->xvalues, h = edge->ymax - edge->ymin;
  1427.                  --h >= 0;)
  1428.                 *Xp++ += dx;
  1429.         }
  1430.     }
  1431. }
  1432.  
  1433.  
  1434. /*
  1435.  * UnJumble() - Sort a Region Top to Bottom
  1436.  *
  1437.  * It is an open question whether it pays in general to do this.
  1438.  */
  1439. void UnJumble(struct region *region)
  1440. {
  1441.     struct edgelist *anchor;    /* new lists built here */
  1442.     struct edgelist *edge;        /* edge pointer for loop */
  1443.     struct edgelist *next;        /* ditto */
  1444.  
  1445.     anchor = NULL;
  1446.  
  1447.     for (edge = region->anchor; VALIDEDGE(edge); edge = next)
  1448.     {
  1449.         if (edge->link == NULL)
  1450.             t1_abort("UnJumble:  unpaired edge?");
  1451.         next = edge->link->link;
  1452.         edge->link->link = NULL;
  1453.         anchor = SortSwath(anchor, edge, t1_SwathUnion);
  1454.     }
  1455.  
  1456.     if (edge != NULL)
  1457.         vertjoin(anchor, edge);
  1458.  
  1459.     region->anchor = anchor;
  1460.     region->flag &= ~ISJUMBLED(ON);
  1461. }
  1462.  
  1463.  
  1464. static void OptimizeRegion(struct region *R)
  1465. {
  1466.     pel *xP;            /* pel pointer for inner loop */
  1467.     int x;                /* holds X value */
  1468.     int xmin, xmax;        /* holds X range */
  1469.     int h;                /* loop counter */
  1470.     struct edgelist *e;    /* edgelist pointer for loop */
  1471.  
  1472.     R->flag |= ISRECTANGULAR(ON);
  1473.  
  1474.     for (e = R->anchor; VALIDEDGE(e); e = e->link)
  1475.     {
  1476.         xmin = MAXPEL;
  1477.         xmax = MINPEL;
  1478.         for (h = e->ymax - e->ymin, xP = e->xvalues; --h >= 0;)
  1479.         {
  1480.             x = *xP++;
  1481.             if (x < xmin)
  1482.                 xmin = x;
  1483.             if (x > xmax)
  1484.                 xmax = x;
  1485.         }
  1486.         if (xmin != xmax || (xmin != R->xmin && xmax != R->xmax))
  1487.             R->flag &= ~ISRECTANGULAR(ON);
  1488.         if (xmin < e->xmin || xmax > e->xmax)
  1489.             t1_abort("Tighten: existing edge bound was bad");
  1490.         if (xmin < R->xmin || xmax > R->xmax)
  1491.             t1_abort("Tighten: existing region bound was bad");
  1492.         e->xmin = xmin;
  1493.         e->xmax = xmax;
  1494.     }
  1495.     R->flag |= ISOPTIMIZED(ON);
  1496. }
  1497.  
  1498.  
  1499. /*
  1500.  * Miscellaneous Routines
  1501.  *
  1502.  * MoreWorkArea() - Allocate New Space for "edge"
  1503.  *
  1504.  * Our strategy is to temporarily allocate an array to hold this
  1505.  * unexpectedly large edge.  ChangeDirection frees this array any time
  1506.  * it gets a shorter 'dy'.
  1507.  */
  1508. void MoreWorkArea(
  1509.         struct region *R,            /* region we are generating */
  1510.         fractpel x1, fractpel y1,    /* starting point of line */
  1511.         fractpel x2, fractpel y2)    /* ending point of line */
  1512. {
  1513.     int idy;    /* integer dy of line */
  1514.  
  1515.     idy = NEARESTPEL(y1) - NEARESTPEL(y2);
  1516.     if (idy < 0)
  1517.         idy = -idy;
  1518.  
  1519.     /*
  1520.      * we must add one to the delta for the number of run ends we
  1521.      * need to store:
  1522.      */
  1523.     if (++idy > currentsize)
  1524.     {
  1525.         IfTrace1((RegionDebug > 0), "Allocating edge of %d pels\n", idy);
  1526.         if (currentworkarea != workedge)
  1527.             NonObjectFree(currentworkarea);
  1528.         currentworkarea = (pel *) Allocate(0, NULL, idy * sizeof(pel));
  1529.         currentsize = idy;
  1530.     }
  1531.     ChangeDirection(CD_CONTINUE, R, x1, y1, y2 - y1);
  1532. }
  1533.  
  1534.  
  1535. /*
  1536.  * BoxClip() - Clip a Region to a Rectangle
  1537.  *
  1538.  * BoxClip also duplicates the region if it is permanent.  Note the
  1539.  * clipping box is specified in REGION coordinates, that is, in
  1540.  * coordinates relative to the region (0,0) point
  1541.  */
  1542. struct region *BoxClip(
  1543.         struct region *R,        /* region to clip */
  1544.         pel xmin, pel ymin,        /* upper left hand corner of rectangle */
  1545.         pel xmax, pel ymax)        /* lower right hand corner */
  1546. {
  1547.     struct edgelist anchor;        /* pretend edgelist to facilitate discards */
  1548.     struct edgelist *e, *laste;
  1549.  
  1550.     IfTrace1((OffPageDebug), "BoxClip of %z:\n", R);
  1551.  
  1552.     R = UniqueRegion(R);
  1553.  
  1554.     if (xmin > R->xmin)
  1555.     {
  1556.         IfTrace2((OffPageDebug), "BoxClip:  left clip old %d new %d\n",
  1557.              (long)R->xmin, (long)xmin);
  1558.         R->xmin = xmin;
  1559.     }
  1560.     if (xmax < R->xmax)
  1561.     {
  1562.         IfTrace2((OffPageDebug), "BoxClip:  right clip old %d new %d\n",
  1563.              (long)R->xmax, (long)xmax);
  1564.         R->xmax = xmax;
  1565.     }
  1566.  
  1567.     if (ymin > R->ymin)
  1568.     {
  1569.         IfTrace2((OffPageDebug), "BoxClip:  top clip old %d new %d\n",
  1570.              (long)R->ymin, (long)ymin);
  1571.         R->ymin = ymin;
  1572.     }
  1573.     if (ymax < R->ymax)
  1574.     {
  1575.         IfTrace2((OffPageDebug), "BoxClip:  bottom clip old %d new %d\n",
  1576.              (long)R->ymax, (long)ymax);
  1577.         R->ymax = ymax;
  1578.     }
  1579.  
  1580.     laste = &anchor;
  1581.     anchor.link = R->anchor;
  1582.  
  1583.     for (e = R->anchor; VALIDEDGE(e); e = e->link)
  1584.     {
  1585.         if (TOP(e) < ymin)
  1586.         {
  1587.             e->xvalues += ymin - e->ymin;
  1588.             e->ymin = ymin;
  1589.         }
  1590.         if (BOTTOM(e) > ymax)
  1591.             e->ymax = ymax;
  1592.         if (TOP(e) >= BOTTOM(e))
  1593.         {
  1594.             discard(laste, e->link->link);
  1595.             e = laste;
  1596.             continue;
  1597.         }
  1598.         if (e->xmin < xmin)
  1599.         {
  1600.             cedgemax(BOTTOM(e) - TOP(e), e->xvalues, xmin);
  1601.             e->xmin = xmin;
  1602.             e->xmax = MAX(e->xmax, xmin);
  1603.         }
  1604.         if (e->xmax > xmax)
  1605.         {
  1606.             cedgemin(BOTTOM(e) - TOP(e), e->xvalues, xmax);
  1607.             e->xmin = MIN(e->xmin, xmax);
  1608.             e->xmax = xmax;
  1609.         }
  1610.         laste = e;
  1611.     }
  1612.  
  1613.     R->anchor = anchor.link;
  1614.  
  1615.     return (R);
  1616. }
  1617.  
  1618.  
  1619. #ifdef notdef
  1620. /*
  1621.  * CoerceRegion() - Force a TextPath Structure to Become a Region
  1622.  *
  1623.  * We also save the newly created region in the textpath structure, if the
  1624.  * structure was permanent.  Then we don't have to do this again.  Why not
  1625.  * save it all the time?  Well, we certainly could, but I suspect it
  1626.  * wouldn't pay.  We would have to make this region permanent (because we
  1627.  * couldn't have it be consumed) and this would probably require
  1628.  * unnecessary CopyRegions in most cases.
  1629.  */
  1630. struct region *CoerceRegion(
  1631.         struct textpath *tp)    /* input TEXTTYPE */
  1632. {
  1633.     struct segment *path;        /* temporary character path */
  1634.     struct region *R;            /* returned region */
  1635.  
  1636.     R = Interior(path, EVENODDRULE);
  1637.     return (R);
  1638. }
  1639. #endif
  1640.  
  1641.  
  1642. /*
  1643.  * RegionBounds() - Returns Bounding Box of a Region
  1644.  */
  1645. struct segment *t1_RegionBounds(struct region *R)
  1646. {
  1647.     extern struct XYspace *IDENTITY;
  1648.  
  1649.     struct segment *path;    /* returned path */
  1650.  
  1651.     path = BoxPath(IDENTITY, R->ymax - R->ymin, R->xmax - R->xmin);
  1652.     path = Join(PathSegment(MOVETYPE, R->origin.x + TOFRACTPEL(R->xmin),
  1653.                 R->origin.y + TOFRACTPEL(R->ymin)),
  1654.             path);
  1655.     return (path);
  1656. }
  1657.  
  1658.  
  1659. /*
  1660.  * Formatting/Dump Routines for Debug
  1661.  *
  1662.  * DumpArea() - Display a Region
  1663.  */
  1664. void DumpArea(struct region *area)
  1665. {
  1666.     IfTrace1(TRUE, "Dumping area %x,", area);
  1667.     IfTrace4(TRUE, " X %d:%d Y %d:%d;", (long)area->xmin,
  1668.          (long)area->xmax, (long)area->ymin, (long)area->ymax);
  1669.     IfTrace4(TRUE, " origin=(%p,%p), ending=(%p,%p)\n",
  1670.         area->origin.x, area->origin.y, area->ending.x, area->ending.y);
  1671.     DumpEdges(area->anchor);
  1672. }
  1673.  
  1674.  
  1675. #define  INSWATH(p, y0, y1)  (p != NULL && p->ymin == y0 && p->ymax == y1)
  1676.  
  1677.  
  1678. /*
  1679.  * DumpEdges() - Display Run End Lists (Edge Lists)
  1680.  */
  1681. static pel RegionDebugYMin = MINPEL;
  1682. static pel RegionDebugYMax = MAXPEL;
  1683.  
  1684. void DumpEdges(struct edgelist *edges)
  1685. {
  1686.     struct edgelist *p, *p2;
  1687.     pel ymin = MINPEL;
  1688.     pel ymax = MINPEL;
  1689.     int y;
  1690.  
  1691.     if (edges == NULL)
  1692.     {
  1693.         IfTrace0(TRUE, "    NULL area.\n");
  1694.         return;
  1695.     }
  1696.     if (RegionDebug <= 1)
  1697.     {
  1698.         for (p = edges; p != NULL; p = p->link)
  1699.         {
  1700.             edgecheck(p, ymin, ymax);
  1701.             ymin = p->ymin;
  1702.             ymax = p->ymax;
  1703.             IfTrace3(TRUE, ". at %x type=%d flag=%x",
  1704.                  p, (long)p->type, (long)p->flag);
  1705.             IfTrace4(TRUE, " bounding box HxW is %dx%d at (%d,%d)\n",
  1706.                  (long)ymax - ymin, (long)p->xmax - p->xmin,
  1707.                  (long)p->xmin, (long)ymin);
  1708.         }
  1709.     }
  1710.     else
  1711.     {
  1712.  
  1713.         for (p2 = edges; p2 != NULL;)
  1714.         {
  1715.  
  1716.             edgecheck(p2, ymin, ymax);
  1717.             ymin = p2->ymin;
  1718.             ymax = p2->ymax;
  1719.  
  1720.             if (RegionDebug > 3 || (ymax > RegionDebugYMin
  1721.                         && ymin < RegionDebugYMax))
  1722.             {
  1723.                 IfTrace2(TRUE, ". Swath from %d to %d:\n",
  1724.                      ymin, ymax);
  1725.                 for (p = p2; INSWATH(p, ymin, ymax); p = p->link)
  1726.                 {
  1727.                     IfTrace4(TRUE, ". . at %x[%x] range %d:%d, ",
  1728.                          p, (long)p->flag,
  1729.                           (long)p->xmin, (long)p->xmax);
  1730.                     IfTrace1(TRUE, "subpath=%x,\n", p->subpath);
  1731.                 }
  1732.             }
  1733.             for (y = MAX(ymin, RegionDebugYMin); y < MIN(ymax, RegionDebugYMax); y++)
  1734.             {
  1735.                 IfTrace1(TRUE, ". . . Y[%5d] ", (long)y);
  1736.                 for (p = p2; INSWATH(p, ymin, ymax); p = p->link)
  1737.                     IfTrace1(TRUE, "%5d ",
  1738.                          (long)p->xvalues[y - ymin]);
  1739.                 IfTrace0(TRUE, "\n");
  1740.             }
  1741.             while (INSWATH(p2, ymin, ymax))
  1742.                 p2 = p2->link;
  1743.         }
  1744.     }
  1745. }
  1746.  
  1747.  
  1748. /*
  1749.  * edgecheck() - For Debug, Verify that an Edge Obeys the Rules
  1750.  */
  1751. static void edgecheck(struct edgelist *edge, int oldmin, int oldmax)
  1752. {
  1753.     if (edge->type != EDGETYPE)
  1754.         t1_abort("EDGE ERROR: non EDGETYPE in list");
  1755.     /*
  1756.      * The following check is not valid if the region is jumbled so I took it
  1757.      * out:
  1758.      */
  1759. /*     if (edge->ymin < oldmax && edge->ymin != oldmin)
  1760.                t1_abort("EDGE ERROR: overlapping swaths"); */
  1761. }
  1762.